FIG. 1 is a configuration diagram for a conventional multiplier device 10. In the drawing, a reference character 1 is a 32-bit register (Y-register) for storing a multiplicand Y. A reference character 2 is a 32-bit register (X-register) for storing a multiplier X and also for storing the final result of a mathematical operation.
A reference character 3 is a 32-bit register (Z-register) for accumulated additions which stores operational results Z during a multiplication operation.
A reference character 4 is an ADDER which is a 32-bit adder for adding the contents Y and Z of the registers 1 and 3. A reference character 5 is a selector which outputs a field ADD&lt;0:31&gt; in the adder 4 as a output value when the bit X&lt;31&gt; in the register 2 is "1", or which outputs the contents Z&lt;0:31&gt; in the Z-register 3 when X&lt;31&gt; of the register 2 is "0".
The operation of a conventional multiplier device 10 with the above configuration shown in FIG. 1 will now be explained.
First, an output CARRY of the ADDER 4 is written into a Z&lt;0&gt; bit in the Z-register 3. At the same time, the bit field &lt;0,30&gt; in the X-register 2 is written into the bit field &lt;1,31&gt; in the X-register 2, and then the bit field SEL&lt;0:30&gt; in the output of the selector 5 is written into the Z&lt;1:31&gt; bit field in the Z-register 3; and the bit SEL&lt;31&gt; in the output from the selector 5 is written into the bit &lt;0&gt; in the X-register 2.
As a result, the contents of the bit field &lt;1:30&gt; of the X-register 2 are shifted one bit to the right.
The above operation will now be explained in detail using a timing chart shown in FIG. 2.
A multiplication 6.times.133=798 is being executed here. In the chart, TIME is the execution time; Y represents the contents of the Y-register 1 in which the multiplicand is stored; Z is the contents of the accumulated result by the adder 4, which is stored in the Z-register 3; and X is the contents of the multiplier stored in the X-register 2.
E1 designated at the right side in FIG. 2 is a control signal authorizing a write-in to the Y-register 1, When E1=1, the write-in is authorized; when E1=0 the value in the register Y is unchanged.
E2 designated at the right side in FIG. 2 is a control signal authorizing a write-in to the Z-register 3. When E2=1, the write-in is authorized; when E2=0 the contents of the Z-register 3 are unchanged.
E3 designated at right side in FIG. 2 is a control signal authorizing a write-in to the X-register 2. When E3=1, the write-in is authorized; when E3=0 the contents of the X-register 2 are unchanged.
For example, as shown in FIG. 2, when TIME=00, the contents of the X- and Y-registers 2 and 1, and Z are not set. E2 is set at 1.
When TIME=01, the value 0 is written into the Z-register 3.
Also, E1 is set at 1. When TIME=02, the multiplicand 6 (0000 . . . 0110) is written into the Y-register 1. E3 is then set at 1.
When TIME=03, the multiplier 133 (0000 . . . 010000101) is written into the X-register 2.
A multiplication instruction is executed from this time. During multiplication, E2 and E3 are set at 1. The value X&lt;31&gt; is 1, and the ADDER 4 adds the contents of the Y-register 1 and Z-register 3 and outputs the result (0000 . . . 0110) to the selector 5.
When TIME=04, the value SEL&lt;0:30&gt; in the output from the selector 5 which is the result of the addition by the ADDER 4 is written into the register Z&lt;1:31&gt;. Next, the value X&lt;0,30&gt; in the X-register 2 is shifted to the right by 1, and the value SEL&lt;31&gt; in the output from the selector 5 is written into the bit X&lt;0&gt; in the X-register 2
At this time X&lt;31&gt;=0, therefore a selector 5 outputs the value in the Z-register 3 without change.
This operation is repeated 32 times.
When TIME=35, the value 798 (0000 . . . 01100011110) which is the result of the multiplication is stored in the X-register 2.
The value stored in the Z-register 3 at this time is the upper order 32 bits of the multiplication result.
As explained above, a shifting operation is executed by the conventional multiplier device, for example as shown in FIG. 1, with this configuration, even when the value of the multiplier is 0, therefore many useless operations are performed. In other words it takes much time to execute multiplication by the conventional multiplier. This is a problem.
In the above-mentioned case, specifically, the execution of the operation is repeated 32 times, irrespective of the type of data, so that the execution takes a very long time.
Accordingly, a multiplier device 30 of the configuration shown in FIG. 3, for example, is commonly used conventionally to speed up the rate of execution.
In FIG. 3, QR is a 32-bit register 31 for storing a multiplier. PRE is a priority encoder 32 which searches the bits output from the QR-register 31 from the left, obtains the leading zero count, and outputs the inverted value of the bits in the bit row indicated by that number. The QR-register 31 has the function of clearing bits initially set at 1 among the bits searched by the priority encoder (PRE) 32.
In addition, the QR-register 31 has the function of detecting when the value in the QR-register 31 itself has become zero and outputting a signal QRZERO for externally transmitting this fact.
Y is a 5-bit register 33 for holding the output from the priority encoder PRE. Z is a 32-bit register 34 for storing a multiplicand. SHF is a shifter 35 for shifting the output from the Z-register 34 to the left by only the number of bits shown in the output from the Y-register 33.
XR is a 32-bit register 36 for storing the results of accumulated additions from multiplication operations.
ADDER is an adder 38 for adding the contents of the XR- and XL-registers 36 and 37.
The output from the adder (ADDER) 38 is output to the XR-register 37. An OR gate 39 has the function of performing an OR operation on a shift-out bit &lt;0:31&gt; output from the shifter (SHF) 35 and a CARRY signal output from the adder (ADDER) 38, and externally transmitting the generated overflow.
Next, the configuration of the QR-register 31 will be explained with reference to FIG. 4.
In the diagram, QREG is a 32-bit register 41. INV is an inverter 42 for inverting the value of a RESET signal PRE&lt;0:4&gt; output from the priority encoder (PRE) 32 shown in FIG. 3. MSKB is a mask generator 43 which sets a "0" for the value of a bit number indicated by the output of the inverter (INV) 42 only, and sets all other bits at "1". AND is an operation device 44 for executing an AND operation on the output from the QREG-register 41 and the MSKB&lt;0,31&gt; from the mask generator (MSKB) 43 per bit.
ZDET is a zero detection circuit 45 for detecting when the value of the QREG-register 41 is "0".
FIG. 5 is a truth table showing the operation of the mask generator (MSKB) 43 which is a structural element of the QR-register 31 shown in FIGS. 3 and 4.
First, a value indicating a bit number initially set at "1" is supplied as input to the mask generator (MSKB) 43 by the priority encoder (PRE) 32. As shown in the table in FIG. 5, only the bit number or value of the input is set to "0" in the output from the mask generator (MSKB) 43. For example, when the input value is "0001", the "0" is set in the 2nd bit position counted from the left side in the output value.
Next, an AND operation is executed for the mask generator MSKB and the QREG-register 41, and the result is rewritten into the QREG-register 41. The searched bits in the QREG-register 41 are therefore "0".
The operation of the priority encoder (PRE) 32 will now be explained with reference to FIG. 6.
First, the value shown as input is input to the priority encoder (PRE) 32. In the drawing, "X" may be either "0" or "1". These values are not set in the diagram. The priority encoder (PRE) 32 then searches the input from the left and outputs the inverse of the value in the bit number initially set as "1".
The priority encoder (PRE) 32 executes this operation in one cycle.
The operation of the shifter (SHF) 35 will now be explained with reference to FIG. 7. The shifter count is input to the shifter (SHF) 35. This shifter count is supplied from the Y-register 33. When the input of the shifter are set as d00, d11, . . . d30, d31, the shifter (SHF) 35 shifts the input to the left according to the count, and, as shown in the diagram, the shifted result is output to the output column.
The number of bits equivalent to the shift count is set to "0" in the output on the right side.
The multiplication method for a conventional multiplier device 30 with the above-described configuration will now be explained with reference to FIGS. 8A and 8B.
The explanation will be given for a multiplication of a 32-bit integer. In the diagram, (a00, a01 . . . a30, a31) represent bits of a multiplicand, shown in binary, while (b00, b01 . . . b30, b31) represent bits of a multiplier, shown in binary. 32-bit numbers are input for the input values of the multiplicand and the multiplier.
Next, in the multiplication, the result of multiplying the multiplicand by b31, and the result of multiplying the next b30 by the result of shifting the multiplicand one bit to the left, are added together 32 times up to b00, to obtain the answer.
The addition result is obtained in 64 bits, but when the accumulated result register for these multiplications is a 32-bit register, only the lower order 32 bits of the multiplication result are stored in the accumulated result register. In this case, when "1"s are set in the upper order 32 bits of the multiplication result, an overflow error occurs.
In FIGS. 8A and 8B, executing a multiplication operation related to the bits with a value of "0" among the multipliers (b00 . . . b31) is an unnecessary operation. When the multiplier bit is "0", the result of multiplying this bit with the multiplicand is also "0", therefore accumulating the addition is unnecessary. Accordingly, if the multiplication operation were carried out only on multiplier bits which have an actual value, the number of clock cycles required for execution would be reduced.
Referring to FIGS. 9A and 9B, an example is given below of the multiplication of 6.times.133=798, using the multiplier device shown in FIG. 3. In these diagrams:
TIME indicates the execution time.
Z indicates the contents of the Z-register 34 for storing the multiplicand.
QR indicates the contents of the QR-register 31 for storing the multiplier.
Y is entered as the inverse of the leading zero count of the multiplier bits from the left.
XL is the result of the output of the shifter (SHF) 35. XR is the result of accumulated additions.
ZE is a signal authorizing the write-in of Z in the Z-register 34. When ZE=1, the write-in occurs; when ZE=0, the previous value is maintained for Z.
QRE is a signal authorizing the write-in of QR in the QR-register 31. When QRE=1, the write-in occurs; when QRE=0, the previous value is maintained for QR.
YE is a signal authorizing the write-in of Y in the Y-register 33. When YE=1, the write-in occurs; when YE=0, the previous value is maintained for Y.
XLE is a signal authorizing the write-in of XL in the XL-register 37. When XLE=1, the write-in occurs; when XLE=0, the previous value is maintained for XL.
XRE is a signal authorizing the write-in of XR in the XL-register 36. When XRE=1, the write-in occurs; when XRE=0, the previous value is maintained for XR.
The flow of the multiplication process will now be explained according to the time TIME shown in FIGS. 9A and 9B.
TIME=00: at this time, the contents of all of the registers 31, 33, 34, 37, and 36 are not set.
ZE is made 1.
TIME=01: the multiplicand 6 (0000 . . . 0110) is written into the Z-register 34. QRE=1.
TIME=02: the multiplier 133 (0000 . . . 10000101) is written into the QR-register 31. XRE=1.
TIME=03: the initial value 0 is written into an accumulation register TMPR. QRE=1, and the bits of the QR-register 31 which have been searched are reset. YE=1.
TIME=04: The content of the QR-register 31 is cleared. The bit number (00111) is written into RLT. QRE=1, and the bits of QR which have been searched are cleared. YE=1, and the bit number is written into YE. XLE=1, and Z is shifted by the count shown in Y and is written into XL.
TIME=05: the content in the QR-register 31 is cleared. The bit number (00111) is written into Y-register 33. QRE=1, and the bits of QR which have been searched are cleared.
The shifted result is written into XL-register 37. A multiplication instruction is executed at TIMES=05, 06, and 07. The shifter (SHF) 35, the priority encoder (PRE) 32, and the adder (ADDER) 38 are operated simultaneously.
During the multiplication, when the QR-register 31 becomes "0", a signal (QRZERO) indicating that the QR-register 31 is zero is set at "1" in the zero detection circuit (ZDET) 45, as shown in FIG. 4, in the QR-register 31. This means that the multiplication has been completed.
In this manner, in the conventional multiplier device, as shown in FIGS. 8A and 8B, if the multiplier bit 0 (b00) is "1", the priority encoder (PRE) 32 outputs (11111) (shown in FIG. 7). When (11111) is input, the shifter (SHF) 35 shifts (a00 . . . a31) 31 bits to the left (shown in FIGS. 8A and 8B). The shifted result is accumulated in the accumulation register (TMPR). If b00 is "0", no operation is performed on this bit. In the same manner, the priority encoder (PRE) 32 outputs the result according to FIG. 7, depending on the numbers of the bits for which the value is "1" during a search of (b00 . . . b31).
The shifter (SHF) 35 shifts the multiplicant according to FIG. 7, and multiplication is implemented by accumulating the addition of the results.
The detection of an overflow in a conventional multiplier device with the above-mentioned configuration and operation, converted to high speed, will now be explained.
In the case of a 32-bit.times.32-bit multiplication result, 64 bits are obtained. However, when the number of bits in the location where the result is stored is 32, an overflow error occurs if the multiplication result cannot be displayed in 32 bits.
It therefore becomes necessary to have a means for detecting this error.
In the case of the conventional multiplier device shown in FIG. 1, the upper order 32 bits of the multiplication result are stored in the Z-register and the lower order 32 bits are stored in the X-register. Therefore an overflow is produced in this multiplier device if even a single "1" exists in the bits of the Z-register after multiplication.
Specifically, the result of the multiplication of a 32-bit multiplicand and a 32-bit multiplier is obtained in 64 bits. However, when the location at which the result is stored has 32 bits, detection of an overflow error is necessary if the result cannot be displayed in 32 bits.
For example, with the conventional multiplier device shown in FIG. 1, the upper order 32 bits of the multiplication result are obtained in the Z-register and the lower order 32 bits are obtained in the X-register.
Therefore, the Z-register is examined after the multiplication operation, and, if not zero, an overflow occurs. In the case shown in FIG. 3, a detection means such as the one shown in FIG. 1 cannot be used because the multiplication result register has 32 bits.
In the case shown in FIG. 3, the following are considered as causes for the generation of an overflow.
(1) The case where the result cannot be displayed in 32 bits when the multiplicand is shifted.
Specifically, the case where a column overflow is produced by the shift operation (here, a shift-out is output from the shifter).
(2) The case where a shift output is produced when the result of shifting the multiplicand is accumulated. Then, with the conventional multiplier device shown in FIG. 3, the production of an overflow is detected by an OR operation between the above-mentioned shift-out bit output and a carry from the adder (ADDER).
In the conventional multiplier device with an overflow detection function illustrated in FIG. 3, a shift-out bit field &lt;0:31&gt; from the shifter (SHF) is supplied to one input of the OR-circuit. A carry bit from the adder (ADDER) is supplied to the other input of the OR-circuit.
The OR-circuit performs an OR operation on these two inputs and detects the production of an overflow. To explain this, with reference to FIGS. 8A and 8B, an overflow occurs if "result &lt;0:31&gt;" appears to the left of the part written in, specifically, if a "1" appears in the upper order 32 bits of the multiplication result.
In this detection method, when the following (1) or (2) occur, this means an overflow is generated.
(1) A "1" is present in the shift-out bit (the part shifted and overflowing to the left side).
(2) The carry output (column only) of the adder becomes "1" during accumulation addition.
As outlined above, with the conventional multiplier device shown in FIG. 1, the multiplication result is obtained in 64 bits.
Accordingly, an overflow is easily detected by examining the contents of the upper order 32 bits.
However, there is the drawback that considerable time is required for the multiplication process in this multiplier device.
As explained in the foregoing, with the conventional multiplier device, the area of the shifter is doubled to output a shift-out bit from the shifter. For this reason there is the problem that large-scale hardware is necessary.
In addition, the load on the shifter is increased and therefore there is the drawback that the operating speed of the shifter itself is reduced.